import pytest
import yaml


def get_data_yaml(file_path):
    with open(file_path, "r", encoding="utf-8")as f:
        data = yaml.safe_load(f)
    return data


def seq_search(data_list, target):
    for i in range(len(data_list)):
        if data_list[i] == target:
            return i
    return -1


def search_len(nums):
    num = 0
    for i in range(len(nums)):
        if len(str(nums[i])) % 2 == 0:
            num += 1
    return num


def search_index(nums, target):
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1


# 二分查找的实现
@pytest.mark.parametrize(
    "data, target, expected_result",
    get_data_yaml("./data/search.yaml")["binary_search"]
)
def test_binary_search(data, target, expected_result):
    """
    1.确定搜索区间的左右边界:low,high，然后计算中间元素的下标:mid。
    2.判断目标元素是否等于中间元素，如果相等则返回下标。
    3.如果不相等，则判断目标元素在左半边还是右半边，继续在该区间中查找。
    4.重复此过程直到找到目标元素或确定目标元素不存在于数组中。
    :return: 返回索引
    """
    low = 0
    high = len(data)
    mid = 0
    while low < high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid
    assert mid == expected_result


def binary_search(data, target):
    low = 0
    high = len(data) - 1
    while low <= high:
        mid = (low + high) // 2
        if data[mid] == target:
            return mid
        elif data[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1



def test_search():
    assert binary_search([1, 2, 3, 4, 5, 6, 7], 7) == 6
    assert binary_search([1, 2, 3, 4, 5, 6, 7], 2) == 1
    assert binary_search([1, 2, 3, 4, 5, 6, 7], 1) == 0
    assert binary_search([2, 3, 6, 7, 8, 9, 11, 13], 13) == 7
    assert binary_search([1, 2, 3, 4, 5, 6, 7], 11) == -1

    # assert search_index([7,8,2,4,5,79,18,32], 5) == 4
    # assert search_index([7,8,2,4,5,79,18,32], 55) == -1

    # assert seq_search([1, 2, 3, 4, 5, 6, 7], 7) == 6
    # assert seq_search([1, 2, 3, 4, 5, 6, 7], 8) == -1
    # assert search_len([12, 345, 2, 6, 7896]) == 2

#
# class Solution:
#     def firstBadVersion(self, n: int) -> int:
#         low,high = 1, n-1
#         while low <= high:
#             mid = (low+high)//2
#             # 如果当前版本为错误版本，那么其为第一个错误版本，或者错误版本在其左方
#             if isBadVersion(mid):
#                 high = mid - 1
#             # 如果当前版本为正确版本，则错误版本在其右方
#             else:
#                 low = mid + 1
#         return low


